﻿using System;
using System.Collections.Generic;

namespace CubeCalculations
{
   public class EvolutionaryCubexSolution
   {
      private const int ThreadCount = 2;
      private readonly Cubex BaseCube;
      private readonly Random random;
      private readonly Dictionary<List<int>, int> SolutionList = new Dictionary<List<int>, int>();
      private readonly Queue<List<int>> SolutionQueue = new Queue<List<int>>();

      public EvolutionaryCubexSolution()
      {
         BaseCube = new Cubex();
         random = new Random((int) DateTime.Now.Ticks);
      }

      public Cubex Cube
      {
         get { return BaseCube; }
         set { value.CopyTo(BaseCube); }
      }

      public List<CubeMoves> SolveCube()
      {
         BaseCube.SolveCube();
         return BaseCube.Solution();
      }

      public List<int> EvaluateSolutions(out int SolutionImprovement)
      {
         var solutionCube = new Cubex();
         int BaseSolution = SolveCube(BaseCube);
         var PreSolutionList = new List<int>();
         var BackTrackingPoints = new List<int>();

         int MinMoves = 1, MaxMoves = 4;

         int BestSolutionLen, SolutionLen, OverAllBestSolutionLen, NoImprovementCount = 0, BackTrackingCount = 0;
         int[] BestSolution, Solution, BackTrackBackup;
         bool IsBacktracking = false;
         var BacktrackingPoints = new SortedList<int, List<int>>();

         BacktrackingPoints.Add(BaseSolution, new List<int>());


         OverAllBestSolutionLen = BestSolutionLen = BaseSolution;

         int next = 40; // random.Next(20, 40);
         for (int j = 0; j < next; j++)
         {
            /// Generiere Neue Lösungen und behalte bestes
            {
               BestSolution = null;
               BestSolutionLen = int.MaxValue;
               for (int i = 0; i < 20; i++)
               {
                  PrepareCube(BaseCube, solutionCube, PreSolutionList);
                  Solution = RandomMoves(MinMoves, MaxMoves, solutionCube);
                  SolutionLen = SolveCube(solutionCube, PreSolutionList.Count);

                  if (SolutionLen < BestSolutionLen)
                  {
                     BestSolution = Solution;
                     BestSolutionLen = SolutionLen;
                  }
               }
               if (BestSolutionLen < OverAllBestSolutionLen)
               {
                  PreSolutionList.AddRange(BestSolution);
                  OverAllBestSolutionLen = BestSolutionLen;
                  MinMoves = 1;
                  MaxMoves = 4;
               }
               else if (++NoImprovementCount > 20)
               {
                  NoImprovementCount = 0;
                  MinMoves += 2;
                  MaxMoves += 2;
               }
            }
         }

         PrepareCube(BaseCube, solutionCube, PreSolutionList);
         SolutionImprovement = SolveCube(solutionCube, PreSolutionList.Count) - BaseSolution;

         return PreSolutionList;
      }


      public List<int> EvaluateSolutionsBacktracking(out int SolutionImprovement)
      {
         var solutionCube = new Cubex();
         int BaseSolution = SolveCube(BaseCube);

         int MinMoves = 1, MaxMoves = 4;
         //SortedList<int, List<int>> BacktrackingPoints = new SortedList<int, List<int>>();
         var BacktrackingPoints = new BacktrackingList();

         BacktrackingPoints.Add(BaseSolution, new List<int>());

         int[] Solution;
         int SolutionLen,
             BestSolutionLen = BaseSolution,
             BacktrackingIndex = 0,
             NoImprovementCount = 0,
             BacktrackingIncreased = 0;

         int next = 200; // random.Next(20, 40);
         for (int j = 0; j < next; j++)
         {
            PrepareCube(BaseCube, solutionCube, BacktrackingPoints.AtIndex(BacktrackingIndex));
            Solution = RandomMoves(MinMoves, MaxMoves, solutionCube);
            SolutionLen = SolveCube(solutionCube, BacktrackingPoints.AtIndex(BacktrackingIndex).Count);

            if (BacktrackingPoints.ContainsKey(SolutionLen))
            {
               BacktrackingPoints[SolutionLen] = BacktrackingPoints[SolutionLen].Count > Solution.Length
                                                    ? new List<int>(Solution)
                                                    : BacktrackingPoints[SolutionLen];
            }
            else
            {
               BacktrackingPoints.Add(SolutionLen, new List<int>(Solution));
            }

            if (SolutionLen < BestSolutionLen)
            {
               BacktrackingIndex = 0;
               BestSolutionLen = SolutionLen;
            }
            else if (++NoImprovementCount > 10)
            {
               NoImprovementCount = 0;
               BacktrackingIndex++;

               if (++BacktrackingIncreased >= 3)
               {
                  MinMoves += 2;
                  MaxMoves += 2;
               }
            }
         }


         //PrepareCube(BaseCube, solutionCube, BacktrackingPoints.AtIndex(0));
         SolutionImprovement = SolveCube(solutionCube, BacktrackingPoints.AtIndex(0).Count) - BaseSolution;
         return BacktrackingPoints.AtIndex(0);
      }


      private void PrepareCube(Cubex BaseCube, Cubex PreparedCube, List<int> PreSolution)
      {
         BaseCube.CopyTo(PreparedCube);
         foreach (int i in PreSolution)
         {
            PreparedCube.CubeRotation[i]();
         }
      }

      public void PrepareCube(Cubex Cube, List<int> PreSolution)
      {
         Cube.CopyTo(BaseCube);
         foreach (int i in PreSolution)
         {
            BaseCube.CubeRotation[i]();
         }
      }

      private int SolveCube(Cubex Cube)
      {
         return SolveCube(Cube, 0);
      }

      private int SolveCube(Cubex Cube, int BaseSteps)
      {
         Cube.SolveCube();
         return Cube.Solution().Count + BaseSteps;
      }

      private int[] RandomMoves(int MinMoves, int MaxMoves, Cubex cubex)
      {
         int resCnt = random.Next(MinMoves, MaxMoves);
         var result = new int[resCnt];
         for (int i = 0; i < result.Length; i++)
         {
            result[i] = RandomMove(cubex);
         }
         return result;
      }

      private int RandomMove(Cubex cubex)
      {
         int result = random.Next(0, cubex.CubeRotation.Length);
         cubex.CubeRotation[result]();
         return result;
      }

      #region Nested type: BacktrackingList

      public class BacktrackingList : SortedList<int, List<int>>
      {
         public List<int> AtIndex(int Index)
         {
            int Start = 0;
            foreach (var pair in this)
            {
               if (Start++ == Index)
                  return pair.Value;
            }
            throw new IndexOutOfRangeException();
         }
      }

      #endregion

      #region Nested type: BacktrackingPoint

      internal struct BacktrackingPoint
      {
         internal int Fitness;
         internal List<int> SolutionSteps;
      }

      #endregion
   }
}